1.xa0一种室内环境下基于加权生成树的WLAN定位平滑稳定方法,采用的无线局域网络(WLAN)包括若干个已知自身物理位置信息的无线接入点(Accessxa0Point,AP)和若干个移动节点,所述移动节点周期性地发送信号探测包,所述无线接入点根据接收到的信号探测包获取移动节点的接收信号强度指示(RSSI)信息,定位服务器综合各AP信息,计算出移动节点的定位位置,其特征在于所述方法包括以下步骤:(1)在实际定位环境下,根据需要将地图划分为有代表性的区域,根据区域之间的连通关系建立一个区域连通图,其中区域作为图结构中的顶点,若两个区域在实际中是相邻连通的,则区域连通图中它们之间有边相连;(2)在各区域中心放置移动节点,保持其位置不变,各AP采集一段时间的RSSI测值,统计得到各区域的RSSI特征;(3)在每个定位周期中,搜集各AP对移动节点的RSSI测值,通过与各区域的RSSI特征进行比对计算,获得移动节点位于各个区域的比对概率;然后计算最近W个周期比对概率的均值,记为平均比对概率;(4)以上一周期定位区域为根依据广度优先方法构建生成树T,在生成树上按如下规则获得各区域累计概率:根节点区域的累计概率为其平均定位概率,其余各区域的累计概率是以该区域为根的子树上所有区域的平均比对概率之和;(5)若存在一个或多个区域的累计概率大于给定阈值,选取离根节点最远的区域作为移动节点定位显示区域;否则,显示位置不变。
2.xa0根据权利要求1所述的方法,其特征在于所述方法步骤(3)中移动节点位于各个区域的比对概率按照如下步骤获得:假设地图被划分为n个区域(区域编号为1~n),布置了m个AP(AP编号为1~m);某定位周期内,记无线接入点xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="33"/>(i为AP编号)测得移动节点的RSSI值为ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="22"/>,设ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="33"/>测得移动节点在区域j(j为区域编号)内的RSSI值符合正态分布ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="79"/>(其中ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="25"/>为均值,ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="27"/>为方差),那么根据RSSI值ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="22"/>可得到移动节点位于区域j的概率ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="21"/>:xa0xa0xa0xa0ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="192"/>xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0(1);其中均值ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="25"/>与方差ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="27"/>可通过在区域j内用ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="33"/>采集一段时间移动节点的RSSI测值然后统计的方法获得;若共有s个APntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="176"/>测得移动节点的RSSI值,则移动节点位于区域j的联合概率ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="19"/>为:xa0xa0xa0xa0ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="109"/>xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0(2);移动节点位于区域j的比对概率ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="19"/>为各区域联合概率的归一化结果,即: ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="99"/>xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0(3);xa0xa0xa0xa0根据最近W个周期的比对概率来计算移动节点在t时刻位于各区域的平均比对概率ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="37"/>:xa0xa0xa0ntent="drawing" img-format="jpg" inline="no" orientation="portrait" wi="202"/>xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0xa0(4)。技术领域
本发明涉及一种WLAN定位中基于加权生成树的平滑稳定方法,具体涉及一种用于WLAN的室内环境下进行区域定位的非确定性比对算法的平滑稳定方法。xa0
背景技术
随着数据业务和多媒体业务的快速增加,人们对定位与导航的需求日益增大,尤其在复杂的室内环境,如机场大厅、展厅、仓库、超市、图书馆、地下停车场、矿井等环境中,常常需要确定移动终端或其持有者、设施与物品在室内的位置信息。但是受定位时间、定位精度以及复杂室内环境等条件的限制,比较完善的定位技术目前还无法很好地利用。GPS是目前应用最为广泛的定位技术。当GPS接收机在室内工作时,由于信号受建筑物的影响而大大衰减,定位精度也很低,要想达到室外一样直接从卫星广播中提取导航数据和时间信息是不可能的。xa0使用WLAN进行室内定位是一个性价比很高的选择,无需特别添加基础设施。无线局域网络(WLAN)包括若干个已知自身物理位置信息的无线接入点(Accessxa0Point,AP)和若干个移动节点,所述移动节点周期性地发送信号探测包,所述无线接入点根据接收到的信号探测包计算RSSI信息或跳数信息获得移动节点的定位。进行室内定位时,移动节点可以为待定位人员或物体携带的一个具有WiFi通信功能的定位标签,为降低系统成本,该标签可只具有上行信道,周期性发送信标探测帧。由于无线信号的不稳定,且WLAN中难以准确测量时间与距离,因此无法使用传统的卫星定位系统中的基于测距的集合方法来定位。学术界和工业界大多倾向于使用基于信号特征比对的方法。xa0文献[Honkavirtaxa0V,Peralaxa0T,Ali-Loyttyxa0S,etxa0al.Axa0comparativesurveyxa0ofxa0WLANxa0locationxa0fingerprintingxa0methods,Procxa0WorkshopPositioning,Navig.Commun.,WPNC,Hannover,Germany,2009:243-251]总结了近年来这一类方法的进展。这类方法一般分为离线和在线两个阶段。离线阶段,将定位标签放置在采样点上,采集一段时间的信号,获xa0得各采样点的信号特征(如信号接收强度指示RSSI的平均值等)。在线阶段,通过比较实时获取的信号与各采样点的信号特征,得出移动节点位于某个采样点附近的定位结果。其中,比对方法分为两大类,第一类方法获得移动节点位于某个采样点的确定结果,第二类方法获得移动节点位于各个采样点的概率。xa0在实际应用中,由于干扰和环境遮挡等原因,很难获得稳定、同步、完整的RSSI值集合。因此往往需要根据几个定位周期的比对结果,综合分析后得出一个平滑稳定的定位结果。xa0
发明内容
本发明目的在于提供一种室内环境下基于加权生成树的WLAN定位平滑稳定方法,它能有效的综合分析几个定位周期内定位服务器获取的移动节点的RSSI值,通过与事先采集统计的各区域的RSSI特征的比对计算,并结合定位区域的连通关系,得到合理的概率分布,进而得到稳定的区域定位。xa0传统的平滑稳定机制大多没有考虑地图区域的连通性,获得的平滑结果是由离散的采样点位置计算得来的连续结果,当比对效果较差时,平滑效果更不可靠。为了解决现有技术中的这些问题,本发明提供的技术方案如下:xa0一种室内环境下基于加权生成树的WLAN定位平滑稳定方法,采用的WLAN包括若干AP和若干个移动节点,所述移动节点周期性地发送信号探测包,所述AP根据接收到的信号探测包获取移动节点的RSSI值,定位服务器综合各AP信息,计算出移动节点的定位位置。xa0对于上述技术方案,我们具有进一步的详细方案,移动节点位置的计算采用了一种基于加权生成树的平滑稳定机制,即在离线阶段划分地图区域,每个区域使用静置的移动节点采集RSSI值,定位服务器对此进行统计获得各区域的RSSI特征如平均值,在线阶段时,根据实时收集的RSSI值与各区域RSSI特征的比对,获得各区域的基本概率分布,并在时间和空间两个角度进行平滑,最后得到更合理的概率分布,以此确定定位显示结果。具体方法包括以下步骤:xa0步骤1:在实际定位环境下,所述系统根据需要将地图划分为有代表性xa0的区域,根据区域之间的连通关系建立一个区域连通图G。该图的构造方法如下:整个定位环境划分成独立的区域,每个区域A_i都抽象成一个顶点u_i;如果两个区域A_i和A_j通过门、走廊等相连,则在区域连通图G中顶点u_i和u_j也是相连的。xa0步骤2:在各区域中心放置移动节点,保持其位置不变,各AP采集一段时间的RSSI测值,统计得到各区域的RSSI特征。假设地图被划分为n个区域,布置了m个AP,假设AP_i测得移动节点在区域j内的RSSI值符合正态分布xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="247"/>其中μ_ij为均值,σ_ij为方差。xa0步骤3:某定位周期内,AP_i测得移动节点的RSSI值为x_i,可得到移动节点位于区域j的概率P_ij为:xa0 P ij = 1 σ ij 2 π e - ( x i - μ ij ) 2 σ ij 2 - - - ( 1 ) ; ]]> 当接收到信号的AP集合记为xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="472"/>其中i₁,i₂,...i_s∈[1,m]时,移动节点位于区域j的联合概率P_j为:xa0 P j = Π k = 1 s P i k j - - - ( 2 ) ; ]]> 则移动节点位于各区域的比对概率分布为各区域联合概率的归一化结果,移动节点位于区域j的比对概率p_j为:xa0 p j = P j Σ k = 1 n P k - - - ( 3 ) ; ]]> 步骤4:根据最近W个周期的比对概率来计算移动节点在t时刻位于各区域的平均比对概率xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="122"/> p ‾ j ( t ) = Σ k = 0 W - 1 p j ( t - k ) / W - - - ( 4 ) ; ]]> 步骤5:以上一周期定位区域为根依据广度优先方法为图G构建生成树T,即所有与该根节点区域连通的区域作为其子节点区域加入生成树,子节xa0点区域又将尚未加入生成树的与其连通的区域作为自己的子节点区域加入生成树,以此类推,直到所有的区域都加入生成树。在生成树上按如下规则获得各区域累计概率:根节点区域的累计概率为其平均比对概率,其余各区域的累计概率是以该区域为根的子树上所有区域的平均比对概率之和。即t时刻标签定位到区域j的累计概率q_j(t)为:xa0 ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> 步骤6:如果所有区域的累计概率都不超过阈值,则显示位置不变。否则,即存在一个或多个区域的累计概率大于给定阈值,选取离根节点最远的区域作为移动节点定位显示区域。其中,两个区域的距离用生成树T上连接两个顶点的路径上包含的边数来衡量。xa0进一步,上述步骤2、3中所述的计算基本比对概率的方法可以采用其他任意的能确定移动节点各区域概率分布的算法,并不限于基于RSSI值的算法。xa0相对于现有技术中的方案,本发明的优点是:xa0本发明所提供的WLAN定位中基于加权生成树的平滑稳定方法,它通过综合分析最近W个周期的定位结果来确定最终的平滑结果即显示位置,可以有效降低RSSI值自身不稳定对定位结果的不利影响,进而有效排除个别定位错误问题,提高了定位精度,极大地减少了定位过程中常见的跳跃现象;xa0本发明所提供的方法考虑到了各区域之间的邻接关系与连通关系,最终平滑后的显示轨迹都是合理的,轨迹体现了所有的中间过程。xa0本发明相比其它针对定位比对结果做区域重复分析的方法,引入了概率方法,更好的适应了移动节点位于区域边界的情况。xa0
附图说明
下面结合附图及实施例对本发明作进一步描述:xa0图1为本发明实施例的结构布置图;xa0图2为本发明实施例的一次定位结果的平滑演示图。xa0
具体实施方式
以下结合具体实施例对上述方案做进一步说明。应理解,这些实施例是用于说明本发明而不限于限制本发明的范围。实施例中采用的实施条件可以根据具体厂家的条件做进一步调整,未注明的实施条件通常为常规实验中的条件。xa0实施例xa0该室内环境下基于加权生成树的WLAN定位平滑稳定方法,采用的无线局域网络(WLAN)包括若干个已知自身物理位置信息的无线接入点(Accessxa0Point,AP)和若干个移动节点,所述移动节点周期性地发送信号探测包,所述无线接入点根据接收到的信号探测包获取移动节点的接收信号强度指示(RSSI)信息,定位服务器综合各AP信息,计算出移动节点的定位位置,所述方法包括以下步骤:xa0(1)在实际定位环境下,根据需要将地图划分为有代表性的区域,根据区域之间的连通关系建立一个区域连通图,其中区域作为图结构中的顶点,若两个区域在实际中是相邻连通的,则区域连通图中它们之间有边相连;xa0(2)在各区域中心放置移动节点,保持其位置不变,各AP采集一段时间的RSSI测值,统计得到各区域的RSSI特征,如各AP测得移动节点在该区域内RSSI测值的平均值和方差;xa0(3)在每个定位周期中,搜集各AP对移动节点的RSSI测值,通过与各区域的RSSI特征进行比对计算,获得移动节点位于各个区域的比对概率;然后计算最近W个周期比对概率的均值,记为平均比对概率;xa0(4)以上一周期定位区域为根依据广度优先方法构建生成树T,在生成树上按如下规则获得各区域累计概率:根节点区域的累计概率为其平均定位概率,其余各区域的累计概率是以该区域为根的子树上所有区域的平均比对概率之和;xa0(5)若存在一个或多个区域的累计概率大于给定阈值,选取离根节点最远的区域作为移动节点定位显示区域;否则,显示位置不变。xa0所述方法步骤(3)中移动节点位于各个区域的比对概率按照如下步骤获得:假设地图被划分为n个区域(区域编号为1~n),布置了m个AP(AP编号为1~m);某定位周期内,记无线接入点AP_i(i为AP编号)测得移动xa0节点的RSSI值为x_i,设AP_i测得移动节点在区域j(j为区域编号)内的RSSI值符合正态分布xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="233"/>(其中μ_ij为均值,σ_ij为方差),那么根据RSSI值x_i可得到移动节点位于区域j的概率P_ij:xa0 P ij = 1 σ ij 2 π e - ( x i - μ ij ) 2 σ ij 2 - - - ( 1 ) ; ]]> 其中均值μ_ij与方差σ_ij可通过在区域j内用AP_i采集一段时间移动节点的RSSI测值然后统计的方法获得。xa0若共有s个xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="529"/>测得移动节点的RSSI值,则移动节点位于区域j的联合概率P_j为:xa0 P j = Π k = 1 s P i k j - - - ( 2 ) ; ]]> 移动节点位于区域j的比对概率p_j为各区域联合概率的归一化结果,即:xa0 p j = P j Σ k = 1 n P k - - - ( 3 ) ; ]]> 根据最近W个周期的比对概率来计算移动节点在t时刻位于各区域的平均比对概率xa0ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="121"/> p ‾ j ( t ) = Σ k = 0 W - 1 p j ( t - k ) / W - - - ( 4 ) ; ]]> 如图1所示,本实施例首先如图1所示的楼宇平层内放置12个AP设备,随后在五楼的楼道内和房间内划分了13个定位区域并选择了13个采样点(图中用圆圈表示)来采集RSSI信号,图中的连线表示定位移动节点只会在这些连线组成的轨迹上移动。根据物理场景上的连通性,确定对应顶点间的连通性,最终构造的连通图如图1所示。经过一段时间(本实施例为30分钟)的采样准备,计算出了在这13个采样点,每一个采样点相对于每一个AP节点的RSSI信号强度的平均值和方差。xa0在实际定位时,所有移动节点都以一定的周期(实际设为1秒)广播信标帧,且由于移动节点都只有发包功能而不具备收报解包功能,因此成本价格非常便宜。当网络中的AP节点收到来自移动节点的信标帧后,会计算相应的RSSI值,并给此RSSI值加一个AP本地的时间戳,随后将此RSSI值xa0储存在本地。此外,AP节点也以一定的周期向网络服务器发送数据包,该数据包包含该周期内收到的所有移动节点的RSSI信息及其对应的时间戳。xa0当网络服务器收到来自AP的数据包后,会解包该信息,且认为AP的发包时间和网络服务器的收报时间是相同的,即忽略数据包的发送时间。因此,当解码数据包时,会把各AP的时间戳修正为网络服务器的本地时间,从而实现各个AP间的相对同步。xa0当对移动节点进行定位时,在当前t时刻,将收到的该移动节点的实时RSSI值分别(t-1时刻和t时刻之间收到的)和15个采样点处的RSSI值进行比对,假设信号满足正态分布,得到移动节点在各个区域的基本概率,然后对所有区域做归一化得到各区域比对概率。本发明主要创新在于得到比对概率后的累计平滑,比对概率计算方法在此不再赘述。xa0实际中的一次定位平滑过程如下,上一定位周期(t-1时刻)的移动节点显示位置在区域2处,则以区域2为根节点建立广度优先搜索树,其中前3层如图2所示。则区域2累加概率为平均比对概率,其余区域累加概率为自身平均比对概率加上后代节点的平均比对概率。xa0t时刻和前面4次的各区域比对概率(未列出的区域比对概率始终为0)、当前平均比对概率以及累计概率如表1所示。例如,对于区域5,当前构造的生成树如图2所示,其区域5为跟的子树包含3个区域,分别是5,6和9。若设定阈值p为0.6,则移动节点移动到离区域2最远且累计概率大于0.6的区域5。xa0表1.累计概率计算实例xa0 ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> ntent="drawing" img-format="tif" inline="no" orientation="portrait" wi="700"/> 上述实例只为说明本发明的技术构思及特点,其目的在于让熟悉此项技术的人是能够了解本发明的内容并据以实施,并不能以此限制本发明的保护范围。凡根据本发明精神实质所做的等效变换或修饰,都应涵盖在本发明的保护范围之内。xa0